package com.ywk.base.dataStructure.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

//插入排序：先定义第一个值为有序列，后面的为无序列，将无序列中第一个值按顺序插入到有序列中,
//形成新的有序列以此类推,采用的是移位法（算法中尽量避免通过交换数值而实现的代码）
public class InsertSort {

	public static void main(String[] args) {
//		int[] nums={3,5,1,8,4,7};
		int[] nums = new int[80000];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = (int) (Math.random() * 80000);
		}
		Date d1 = new Date();
		SimpleDateFormat s = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");//日期格式
		System.out.println("排序前的时间：" + s.format(d1));
		for (int i = 1; i < nums.length; i++) {
			int value = nums[i];//与选择排序的区别：插入排序这一步保存的是不变的值，而选择排序保存的是会变的值
			int index = i;
			while (index > 0 && value > nums[index - 1]) {
				//移位法：后面的值大于前面的（相当于nums[i]前面的值都往后移了一步，直到找到比该值还要大的数）
				nums[index] = nums[index - 1];
				index--;
			}
			nums[index] = value;
		}
		// System.out.println(Arrays.toString(nums));
		Date d2 = new Date();
		System.out.println("排序后的时间：" + s.format(d2));
	}

}
